This invention relates to the field of computer operating systems, and in particular, to the area of real-time operating systems in embedded computing environments.
Computer operating systems such as UNIX provide a sophisticated degree of protection among processes concurrently executing on the system. A process is defined as a program in execution which utilizes system resources, such as memory and computing time. At each step of execution the process generates the address or addresses, in memory which is needed to successfully execute the step, e.g., a) the address where an instruction to be executed is stored, b) the address where required data is to be found, or c) the address where output data is to be stored. The range of addresses that a computer can generate defines its address space.
Under control of a conventional operating system, e.g., UNIX, the addresses generated by a process do not directly address a location in the computer""s physical memory. Instead, the addresses generated by the process are translated to a physical location using well known virtual memory techniques. A description of virtual memory can be found in the book xe2x80x9cOperating Systems Conceptsxe2x80x9d, by Peterson and Silbersatz. Each process executes its steps and generates addresses as if it is executing on its own private computer which has a very large memory. The size of the memory on this virtual private computer is the size of the process"" address space. The addresses generated by the process in this virtual memory are translated to physical memory locations, also known as real memory addresses, using a page table mechanism, typically implemented in a memory management unit (MMU). Thus, each process is provided a different address space, which is mapped onto the real memory. The MMU translations are briefly described below.
The physical memory is divided into fixed units called pages. The page size is determined by the hardware architecture of the processor. The address space of each process is also divided into pages, each having the same size as a page of the physical memory. For each process, a page table is maintained in memory by the operating system which contains a mapping of the page number in the address space to the page number in the physical memory. The page table also contains some attributes bits for each page. The attribute bits indicate a) whether the page with which they are associated is valid or invalid, i.e., whether or not the associated page has a corresponding page in physical memory, and b) if the process has permission to read or to modify the contents of the page.
When an address is generated by a process, the MMU first looks up the page table in the memory and determines the corresponding physical page in the memory. The permissions for the page are also checked during the look up process to verify that the process is authorized to access the memory in the manner, e.g., read or write, that it is attempting. The physical page number is attached to the offset of the address within the page and a new physical address is generated. The physical address is then used to look up the contents of the memory. Thus, each memory access translates into two sequential accesses, the first one for generating the physical address and checking the validity, with the second one being for actually accessing the physical memory.
The two accesses are usually expedited by means of caching techniques, in which frequently used areas of the page tables (and memory) are stored in a smaller higher speed memory called a cache so as to reduce the probability of actually accessing the physical memory.
One of the advantages of going through a page table is that processes can execute relatively independent of each other. A process has exclusive access to its address space and no other process can modify the contents of the address space, unless the process explicitly provides access to parts of its address space to other processes.
In a system with multiple concurrent processes, switching between processes is a complex, and so xe2x80x9cexpensivexe2x80x9d in processing terms, operation. A process may be further broken down into several threads, each thread being a sequence of executing instructions. All threads within a process execute in the same address space. As such, switching from the currently active thread to another thread is a relatively simple and inexpensive operation. However, all threads have identical privileges to all of the address space of the process to which they belong, and so there is no protection among threads executing in the same address space.
In the area of embedded systems, such as 1) digital television receivers, 2) television set top units, and 3) network switch controllers, there is only one process in the entire system. This process may consist of multiple concurrent threads. However, typically, there is no support for virtual memory because such systems have only so-called xe2x80x9cprimary memoryxe2x80x9d, e.g., RAM, ROM or combination thereof, and no so-called xe2x80x9csecondary storagexe2x80x9d, e.g., a disk. Thus, all the threads have access to the entire memory, including data structures maintained by the operating system.
This global access is a serious problem in the development and debugging of embedded system software. For example, an errant thread, e.g., one still under development, can alter a data structure or code used by an already debugged and xe2x80x9ctrustedxe2x80x9d thread. The trusted code will eventually be affected by the corruption of its data structure or code, and either generate an error or behave unexpectedly. It is very difficult to determine the cause of the problem in such an environment, since the point in the code at which the software crashes or generates a warning is unrelated to the point in the code that caused the problem.
An identical problem exists in digital television receivers which are used for the downloading of multiple applications from a server. The downloaded application may cause the receiver to crash, and it is difficult to isolate the cause of the fault, which could lie in the downloaded application software, the operating system software, or any other supporting library. When the software in the embedded system originates from multiple program development organizations that are cooperating, it is difficult to isolate the cause of the problem. As a result, each organization typically blames the other for the failure.
In embedded systems where an MMU is present, groups of threads can be logically clustered into processes, which are each provided their own address space using MMU page mapping. In this manner, different threads can be provided isolation from one another. In some systems, the MMU is preloaded so that the physical page numbers correspond to the virtual page numbers and the physically generated address is identical to the virtual address. Unfortunately, the cost of having an MMU is usually unacceptable in an embedded system. In those cases, there is no protection provided among the threads.
We have realized that, from both the debugging and development perspective, providing protection among threads executing in the same address space is an attractive idea. Thus, in concurrently filed application Serial No. (case PHA 23-102), assigned to the same assignee as the present application, protection among threads executing in the same address space of a computer system is provided without using virtual memory techniques that require each thread actually, or logically, to be isolated in its own, separate address space. This is achieved by grouping the threads into protection domains, each of the threads in a protection domain having the same rights to access memory as the other threads in that protection domain, so that each thread in a protection domain can access all the information available to the others. At least one protection domain, referred to herein as the xe2x80x9csystemxe2x80x9d domain, which typically is the protection domain of the operating system and has unrestricted access to the entire memory, is predefined prior to execution of any threads. The protection domains, including the system domain, may spawn additional protection domains. However, the total number of protection domains is typically limited to a predetermined maximum number. Also prior to execution, the single address space, which is typically physical memory only and is common to all of the threads, is divided into pages, which typically do not overlap. Each page, either prior to or during execution, has at least one access permission set for it, e.g., on a protection domain-by-protection domain basis or on an exception basis. Only threads that belong to a protection domain having permission to access a page may do so. Permission for read access and write access to each page may be separately specified.
During operation, when a request to access memory is issued by an executing thread, it is determined whether or not the protection domain of the executing thread has permission to perform the requested type of access. If the protection domain of the executing thread is permitted to perform the type of access requested, access is granted and the executing thread""s execution proceeds normally. However, if the protection domain of the executing thread does not have permission to perform the requested type of access, a protection fault is generated.
It is preferable to identify the protection domain of the currently executing thread prior to the memory access. Such identification may be performed each time memory is accessed or each time the thread is changed.
A problem with the foregoing approach to providing protection among threads executing in the same address space relates to the compatibility of such a system with already written, protection-domain-unaware, threads. In particular, all objects created by such a system must be stored somewhere in memory. More specifically, objects must be stored in memory pages that are accessible by the thread, or threads, which require and can manipulate them. One method that can be used to select the pages of memory in which to create an object is an augmented operating system call. In particular, the operating system call is augmented so as to indicate the protection domains which can have access to the object being created. However, this approach suffers from the serious drawback of being incompatible with threads written prior to implementation of the protection domain system. This is because threads written prior to implementation of the protection domain system do not include augmented system calls. Consequently, if augmented system calls were the only way to access memory, such protection domain-unaware threads could not access any memory, and so could not execute.
This drawback is overcome, in accordance with the principles of the invention, by an operating system that provides protection domain support which is arranged to be compatible with xe2x80x9cwell behavedxe2x80x9d threads, i.e., threads that obtain all their memory allocations from the operating system, that were written without regard for protection domains. For example, this may be achieved by associating each protection domain with one or more pages of memory, so-called xe2x80x9cprimary memory pagesxe2x80x9d, for which the protection domain has read and write access permission. Requests by such a to the operating system for a memory allocation, e.g., for memory in which to create a data structure, are automatically fulfilled by the operating system from the memory available in the primary memory pages of the protection domain of the requesting thread. The operating system informs the thread of the location of the created data structure, e.g., by passing to the thread a pointer to the data structure. Note that xe2x80x9cprotection-domain-awarexe2x80x9d threads may have read and/or write access to memory pages that are not primary pages for their protection domains. Likewise, protection-domain-aware threads may also employ the primary pages technique for memory allocation.
Thus, the operating system controls 1) the access permission for each page; 2) the allocation for use as primary pages of pages from xe2x80x9cfree memoryxe2x80x9d pages, e.g., memory pages available in the system domain; and 3) which particular pages are primary pages for each protection domain at any particular time.